package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LC_210_CourseScheduleII {

    public static void main(String[] args) {

    }

    static class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] map = new int[numCourses];
            for (int[] p : prerequisites) {
                map[p[0]]++;
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < map.length; i++) {
                if (map[i] == 0) queue.add(i);
            }
            List<Integer> res = new ArrayList<>();
            int count = queue.size();
            while (!queue.isEmpty()) {
                int temp = queue.poll();
                res.add(temp);
                for (int[] prerequisite : prerequisites) {
                    if (temp == prerequisite[1]) {
                        int t = prerequisite[0];
                        map[t]--;
                        if (map[t] == 0) {
                            queue.add(t);
                            count++;
                        }
                    }
                }
            }
            if (count != numCourses) return new int[0];
            else {
                int[] a = new int[res.size()];
                for (int i = res.size() - 1; i >= 0; i--) {
                    a[i] = res.get(i);
                }
                return a;
            }
        }

    }
}